#深度优先遍历
class Solution:
    def averageOfLevels(self, root):
        res = list()
        net = list()
        self.des(root,0,res,net)
        for i in range(len(res)):
            res[i] = res[i]/net[i]
        return res
    def des(self,root,level,res,net):
        if not root:
            return
        if len(res) <= level:
            res.append(0)
            net.append(0)
        res[level] = res[level]+root.val
        net[level] = net[level] +1
        level = level+1
        self.des(root.left,level,res,net)
        self.des(root.right,level,res,net)


#层次遍历
class Solution:
    def averageOfLevels(self, root):
        from collections import deque
        queue = deque([root])

        average = list()
        while queue:
            length = len(queue)
            sum = 0
            for i in range(length):
                node = queue.popleft()
                sum = sum+node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            average.append(sum/length)
        return average